package com.cqs.leetcode.string.sliding.windws;

import java.util.*;
import java.util.function.BiPredicate;

/**
 * @author lixiaowen
 * @create 2019-12-17
 */
public class FindAllAnagramsinaString438 {

    // 使用上面的模板进行解题，so easy ！
    public List<Integer> findAnagrams2(String s, String p) {
        // 输入参数有效性判断
        if (s.length() < p.length()) {
            return new ArrayList<>();
        }
        // 申请一个散列，用于记录窗口中具体元素的个数情况
        // 这里用数组的形式呈现，也可以考虑其他数据结构
        char[] sArr = s.toCharArray();
        char[] pArr = p.toCharArray();
        int[] hash = new int[26];
        for (int i = 0; i < pArr.length; ++i) {
            hash[pArr[i] - 'a']++;
        }
        // l 表示左指针
        // count 记录当前的条件，具体根据题目要求来定义
        // result 用来存放结果
        List<Integer> results = new ArrayList<>();
        int l = 0, count = 0, pLength = p.length();
        for (int r = 0; r < sArr.length; ++r) {
            // 更新新元素在散列中的数量
            hash[sArr[r] - 'a']--;
            // 根据窗口的变更结果来改变条件值
            if (hash[sArr[r] - 'a'] >= 0) {
                count++;
            }
            // 如果当前条件不满足，移动左指针直至条件满足为止
            if (r > pLength - 1) {
                hash[sArr[l] - 'a']++;
                if (hash[sArr[l] - 'a'] > 0) {
                    count--;
                }
                l++;
            }

            // 更新结果
            if (count == pLength) {
                results.add(l);
            }
        }

        return results;
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || p == null || p.length() == 0 || s.length() == 0 || s.length() < p.length()) return result;
        char[] pcs = p.toCharArray();
        Map<Character,Integer> pMap = new HashMap<>();
        for (char pc : pcs) {
            pMap.put(pc, pMap.getOrDefault(pc,0) + 1);
        }
        char[] scs = s.toCharArray();
        int left = 0,right =  p.length() - 2;
        Map<Character,Integer> sMap = new HashMap<>();
        //初始化窗口[0,p.length-1)的元素
        for (int i = 0; i <= right; i++) {
            char key = scs[i];
            if (pMap.containsKey(key)){
                sMap.put(key,sMap.getOrDefault(key,0) + 1);
            }
        }
        //两个Map是否相同的判断
        BiPredicate<Map<Character,Integer>,Map<Character,Integer>> mapEquals = (map1, map2) -> {
            if (map1.size() != map2.size()) return false;
            //key&值 比较
            Iterator<Character> iterator = map1.keySet().iterator();
            while (iterator.hasNext()){
                Character key = iterator.next();
                if (!map1.getOrDefault(key, 0).equals(map2.getOrDefault(key, 0))){
                    return false;
                }
            }
            return true;
        };
        //找可行解
        while (++right < s.length()){
            //更新sMap
            Character rk = scs[right];
            if (pMap.containsKey(rk)){
                sMap.put(rk, sMap.getOrDefault(rk,0) + 1);
            }
            if (mapEquals.test(sMap,pMap)) result.add(left);
            //left移动一格-- 注意状态的更新是： 影响的left更新之前的字符频率
            Character lk = scs[left++];
            if (pMap.containsKey(lk)){
                //更新状态 -- 至多减到0
                sMap.put(lk, sMap.getOrDefault(lk,1) - 1);
            }
        }
        return result;
    }


    public static void main(String[] args) {
        FindAllAnagramsinaString438 find = new FindAllAnagramsinaString438();
        Map<String,String> testCases = new HashMap<>();
//        testCases.put("bbbAA","AAA");
//        testCases.put("bbbAAA","AAA");
//        testCases.put("bbbAAAA","AAA");
//        testCases.put("bbbAAAAA","AA");
//        testCases.put("","AA");
//        testCases.put("","");
        testCases.put("abcbabcebcadbcdeeadcbadc","abc");
        testCases.put("abcbabcebcadbcdeeadcbadcedg","abc");
        testCases.forEach((k,v)->{
            System.out.println(k + ":" + v + "=" + find.findAnagrams(k,v));
        });
    }
}
